package com.company.剑指offer每日刷题.普通版;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Stack;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

 * 示例 1：
 *
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 *
 * 限制：
 * 0 <= 链表长度 <= 10000
 * */
//这一个节点类，在leetcode OJ系统中，是已经存在的！
class ListNode{
    public int val;
    public ListNode next = null;
    ListNode(int val){
        this.val = val;
    }
}
/**
 * 说明：通过测试，这个题所给定的头结点也是要存储元素的
 * */
public class ReversePrint {
    /**
     * 方法1：List
     * 思路：用List来按照顺序存储链表元素，然后再反向存储进数组中
     * */
    public int[] reversePrint(ListNode head) {
        //头结点为空
        if(head == null){
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        do{
            list.add(head.val);
            head = head.next;
        }while(head != null);

        int len = list.size();
        int res [] = new int[len];
        for (int i = 0; i < len; i++) {
            res[len - i -1] = list.get(i);
        }
        return res;
    }

    /**
     * 方法2：栈
     * 思路：用栈来依次入栈链表元素，然后再出栈所有元素存到数组中，利用先进后出的原理
     * */
    public int[] reversePrint1(ListNode head) {
        //头结点为空
        if(head == null){
            return new int[0];
        }
        Stack<Integer> stack = new Stack<>();
        do{
            stack.push(head.val);
            head = head.next;
        }while(head != null);

        int len = stack.size();
        int res [] = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = stack.pop();
        }
        return res;
    }
}

